package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 这是一个经典算法题目,题目要求:
 * 有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，
 * 假如兔子都不死，问某个月的兔子总数为多少？
 * @author jiaqi.han
 * @date 2021年3月22日
 */
public class Rabbit {

	public static void main(String[] args) {
		int month = 40;
		Rabbit.test1(month);
		Rabbit.test2(month);
	}

	/**
	 * 调用第一种方式并统计时间
	 * @author jiaqi.han
	 * @date 2021年3月22日
	 */
	public static void test1(int month) {
		// 1,1,2,3,5,8,13,21
		long startTime = System.currentTimeMillis();
		Long quantity = Rabbit.getRabbitQuantityByMonth1(month);
		long endTime = System.currentTimeMillis();
		System.out.println(quantity);
		long sumTime = endTime - startTime;
		System.out.println("算法总耗时:" + sumTime);

	}

	/**
	 * 调用第二种方式并统计时间
	 * @author jiaqi.han
	 * @date 2021年3月22日
	 */
	public static void test2(int month) {
		// 1,1,2,3,5,8,13,21
		long startTime = System.currentTimeMillis();
		Long quantity = Rabbit.getRabbitQuantityByMonth2(month);
		long endTime = System.currentTimeMillis();
		System.out.println(quantity);
		long sumTime = endTime - startTime;
		System.out.println("算法总耗时:" + sumTime);

	}

	/**
	 * 通过循环方式,并借助于一个List,实现计数,还可以同计总数
	 * @author jiaqi.han
	 * @date 2021年3月22日
	 */
	public static Long getRabbitQuantityByMonth1(int month) {
		if (month < 3) {
			return 1L;
		}
		Long sum = 0L;
		List<Long> list = new ArrayList<Long>();
		list.add(1L);
		list.add(1L);
		if (month > 2) {
			for (int i = 2; i < month; i++) {
				Long lastTimeNum = list.get(i - 1);
				Long addNum = list.get(i - 2);
				Long newNum = lastTimeNum + addNum;
				list.add(newNum);
			}
		}
		for (int j = 0; j < list.size(); j++) {
			sum = list.get(j);
		}
		System.out.println(list);
		return sum;
	}

	/**
	 * 采用递归方式
	 * @author jiaqi.han
	 * @date 2021年3月22日
	 */
	public static Long getRabbitQuantityByMonth2(int month) {
		if (month < 3) {
			return 1L;
		} else {
			return getRabbitQuantityByMonth2(month - 1) + getRabbitQuantityByMonth2(month - 2);
		}
	}

	/**
	 * 算法总结:这个算法归根结蒂是一个斐波那契数列求值问题.且两种方式进行对比,递归方式的代码显然是十分简洁的,而循环计数方式代码量比较大.
	 * 但是通过对运行数据的记录可以看到,在2~3月的时候,递归更快;在4~10的时候,相差不多,但是在10个月以上的时候,递归的方式明显过慢,耗时呈指数级上升
	 * 而且递归过深的话,会十分消耗内存.
	 * 因此在实际工作中,项目编码的时候,几乎是避免递归的使用的.
	 */

}
